package com.cat.bitOperation;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros/description/
 * @create 2025/8/21 08:45
 * @since JDK17
 */

public class Solution08 {
    List<String> ans = new ArrayList<>();
    void f(int cur, int n, StringBuilder s) {
        if (cur == n) {
            ans.add(new String(s));
            return;
        }
        if (cur != 0 && (((int) s.charAt(cur)) & 1 | ((int) s.charAt(cur - 1)) & 1) == 0) {
            return;
        }
        s.setCharAt(cur, '0');
        f(cur + 1, n, s);
        s.setCharAt(cur, '1');
        f(cur + 1, n, s);
    }
    public List<String> validStrings(int n) {
        StringBuilder s = new StringBuilder("0".repeat(n));
        f(0, n, s);
        return ans;
    }
}
